package com.peng.leetcode.list;

/**
 * BuildListNode
 *
 * @author: lupeng6
 * @create: 2020/12/22 10:14
 */
public class BuildListNode {

    public static void main(String[] args) {
        ListNode listNode = tailInsert(1, 3, 5, 7, 9);
        ListNode listNode2 = tailInsert(2, 4, 6, 8);

        System.out.println("-----------------");

        ListNode sortedList = mergeSortedList(listNode, listNode2);
        while (sortedList != null) {
            System.out.println(sortedList.val);
            sortedList = sortedList.next;
        }
    }

    /**
     * 链表的头 插
     *
     * @author lupeng6
     * @date 2020/12/22 10:22
     */
    public static ListNode headInsert(int... values) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        for (int value : values) {
            ListNode node = new ListNode(value);
            node.next = dummy.next;
            dummy.next = node;
        }
        return dummy.next;
    }

    /**
     * 链表的尾 插
     *
     * @author lupeng6
     * @date 2020/12/22 10:22
     */
    public static ListNode tailInsert(int... values) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode currentNode = dummy;
        for (int value : values) {
            currentNode.next = new ListNode(value);
            currentNode = currentNode.next;
        }
        return dummy.next;
    }

    /**
     * 链表反转
     *
     * @author lupeng6
     * @date 2020/12/22 10:25
     */
    public static ListNode reverse(ListNode head) {
        ListNode dummy = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = dummy;
            dummy = head;
            head = next;
        }
        return dummy;
    }

    /**
     * 快慢指针判断链表是否成环
     *
     * @author lupeng6
     * @date 2020/12/22 10:37
     */
    public static boolean hasCycle(ListNode head) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * 删除链表的倒数第n个节点
     *
     * @author lupeng6
     * @date 2020/12/22 10:43
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode beforeNode = dummy;
        while (head != null) {
            if (n > 0) {
                n--;
            } else {
                beforeNode = beforeNode.next;
            }
            head = head.next;
        }
        beforeNode.next = beforeNode.next.next;
        return dummy.next;
    }

    /**
     * 合并两个升序链表
     *
     * @author lupeng6
     * @date 2020/12/22 11:00
     */
    public static ListNode mergeSortedList(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode currentNode = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val > head2.val) {
                currentNode.next = head2;
                head2 = head2.next;
            } else {
                currentNode.next = head1;
                head1 = head1.next;
            }
            currentNode = currentNode.next;
        }
        currentNode.next = head1 == null ? head2 : head1;
        return dummy.next;
    }
}
